#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "TypeDefin.h"

using namespace std;
/*HJJ QQ479287006
 *给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

 

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2：

输入：lists = []
输出：[]
示例 3：

输入：lists = [[]]
输出：[]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/merge-k-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
//递归合并吧
ListNode *merge(ListNode *&list1, ListNode *&list2) {
    if (!list1)
        return list2;
    if (!list2)
        return list1;

    /// 拼接 链表 1 3       2  4

    if (list1->val < list2->val) {
        list1->next = merge(list1->next, list2);
    } else {
        list2->next = merge(list1, list2->next);
    }


    return (list1->val < list2->val ? list1 : list2);
}


//过了效率很低基本掌握
ListNode *mergeKLists(vector<ListNode *> &lists) {
    if (lists.size() == 0)
        return nullptr;

    if (lists.size() == 1)
        return lists[0];

    ListNode *ret = merge(lists[0], lists[1]);


    for (int i = 2; i < lists.size(); ++i) {
        ret = merge(ret, lists[i]);
    }

    return ret;
}



/*
 * ListNode* onceMerge(ListNode* list1,ListNode* list2)
{
    ListNode* head=nullptr;

    if (list1== nullptr&&list2== nullptr)
        return nullptr;
    if (list1== nullptr)
        return list2;
    if (list2== nullptr)
        return list1;

    if (list1->val<=list2->val)
    {
        head=list1;
        head->next=onceMerge(list1->next,list2);

    }else
    {
        head=list2;
        head->next=onceMerge(list1,list2->next);
    }


    return head;

}

ListNode* mergeFenzhi(vector<ListNode*>& lists,int left ,int right)
{
    if (left==right)
        return lists[left];

// 人家的这个方法确实牛逼！！！！！！
    int mid= left+(right-left)/2;
    ListNode* l1=mergeFenzhi(lists,left,mid);
    ListNode* l2=mergeFenzhi(lists,mid+1,right);
    return onceMerge(l1,l2);

}



ListNode* mergeKLists(vector<ListNode*>& lists) {
    if (lists.size()==0)
        return nullptr;
    if (lists.size()==1)
        return lists[0];
    if (lists.size()==2)
        return onceMerge(lists[0],lists[1]);

    return mergeFenzhi(lists,0,lists.size()-1);
}*/